1. Technical Field
This invention relates generally to providing directory services in a distributed computing environment.
2. Description of the Related Art
A directory service is the central point where network services, security services and applications can form a integrated distributed computing environment. The current use of a directory services may be classified into several categories. A xe2x80x9cnaming servicexe2x80x9d (e.g., DNS and DCE Cell Directory Service (CDS)) uses the directory as a source to locate an Internet host address or the location of a given server. A xe2x80x9cuser registryxe2x80x9d (e.g., Novell NDS) stores information of all users in a system composed of a number of interconnected machine. The central repository of user information enables a system administrator to administer the distributed system as a single system image. Still another directory service is a xe2x80x9cyellow pagesxe2x80x9d lookup provided by some e-mail clients e.g., Netscape Communicator, Lotus Notes, Endora and the like.
With more applications and system services demanding a central information repository, the next generation directory service will need to provide system administrators with a data repository that can significantly ease administrative burdens. In addition, the future directory service must also provide end users with a rich information data warehouse that allows them to access department or company employee data, as well as resource information, such as name and location of printers, copy machines, and other environment resources. In the Internet/intranet environment, it will be required to provide user access to such information in a secure manner.
To this end, the Lightweight Directory Access Protocol (LDAP) has emerged as an IETF open standard to provide directory services to applications ranging from e-mail systems to distributed system management tools. LDAP is an evolving protocol that is based on a client-server model in which a client makes a TCP/IP connection to an LDAP server, sends requests, and receives responses. The LDAP information model in particular is based on an xe2x80x9centry,xe2x80x9d which contains information about some object. Entries are typically organized in a specified tree structure, and each entry is composed of attributes.
LDAP provides a number of known functions including query (search and compare), update, authentication and others. The search and compare operations are used to retrieve information from the database. For the search function, the criteria of the search is specified in a search filter. The search filter typically is a Boolean expression that consists of attribute name, attribute value and Boolean operations like AND, OR and NOT. Users can use the filter to perform complex search operations. The filter syntax is defined in RFC 1960.
LDAP thus provides the capability for directory information to be efficiently queried or updated. It offers a rich set of searching capabilities with which users can put together complex queries to get desired information from a backing store. Increasingly, it has become desirable to use a relational database for storing LDAP directory data. Representative database implementations include DB/2, Oracle, Sybase, Informix and the like. As is well known, Structured Query Language (SQL) is the standard language used to access such databases.
One of main goals for implementing an LDAP directory service with an relational database backing store (e.g., DB/2) is to provide a design and implementation such that all LDAP search queries can be executed efficiently. In the case of repetitive searches involving the same search query, however, it is not cost-effective to return to the backing store repetitively due to the nature of the database management system. In particular, it is very time consuming and expensive to go through the DBMS layers necessary to access entries inside the database for every entry required to be returned.
One approach to solving this problem is to use the backing store""s cache. While this approach has been implemented and has proved somewhat useful, it still requires repetitive access to the backing store from the directory service. Moreover, use of the relational database backing store does not provide significant enough performance enhancements to justify the more complex caching mechanism required.
There remains a need to address the problem of efficient handling of repetitive searches issued from a hierarchical directory service to a relational database backing store.
It is a primary object of this invention to obviate repetitive inquiries into a relational database backing store used by a hierarchical-based directory service.
It is another primary object to search a relational database using hierarchical, filter-based queries, such as LDAP, and efficiently caching search results to increase search efficiency for repetitive queries.
Another primary object of this invention is to cache search results in a more efficient manner in a directory service having a relational database backing store.
Still another important object of this invention is to provide a mechanism for populating a local storage area associated with an LDAP directory service with directory search results retrieved from a relational database (e.g., DE/2) backing store.
Yet another important object of this invention is to enhance the efficiency of a directory service using a caching mechanism.
A more general object of this invention is to provide more efficient, less expensive hierarchical LDAP searches using relational tables in an LDAP directory service having a relational database management system (DBMS) as a backing store.
A still more general object of this invention is to provide a reliable and scaleable enterprise directory solution, wherein a preferred implementation is LDAP using a DB/2 backing store.
These and other objects are provided in a method for searching a relational database using hierarchical, filter-based search queries. The method begins in response to a search query to the relational database. Search results retrieved in response to the search query are cached, preferably in a local storage area of the directory service. In response to subsequent issuance of the search query, the cached search results are then used preferentially in lieu of re-accessing the relational database to increase search efficiency.
According to a feature of the present invention, the search results are cached in a unique manner to facilitate use of these results for subsequent, repetitive queries. Preferably, first and second caches are established in the local storage area. The first cache is sometimes referred to herein as a Type I cache, and the second cache is sometimes referred herein as a Type II cache. The first cache receives a set of identifiers indexed by a filter key of the search query. The search results, namely entries corresponding to the set of identifiers, are then stored in the second cache. The present invention thus provides a mechanism for populating the Type I and Type II caches. In addition, the mechanism modifies information in the caches during (or as a result of) given directory service operations (e.g., modify, modify rdn, delete and add) that would otherwise invalidate the cached information. Thus, whenever a repetitive search query is generated within the directory service, search results are selectively fetched from the caches instead of being retrieved from the relational database. Cached information remains current at all times using the invalidation routines. This operation significantly reduces the cost of processing the repetitive search query.
Preferably, the filter-based query is a Lightweight Directory Access Protocol (LDAP) directory service query and the relational database is DB/2 or some other convenient backing store. As noted above, preferably the local storage area is associated with the directory service for enhanced query response. The Type I and Type II caches are preferably dedicated portions of the directory service local storage area.
In accordance with a more specific aspect of the invention, a method for searching a relational database (e.g., DB/2) from a Lightweight Directory Access Protocol (LDAP) directory service utilizes first and second caches associated with the directory service to obviate use of the backing store when receiving repetitive search queries. Preferably, a given unit of the first cache is a set of identifiers that qualified for the LDAP search of a particular filter key. Each given unit of the second cache is an entry qualified for the search and is indexed by its identifier.
The present invention also describes a computer program product in a computer readable media that implements an algorithm for populating the Type I and Type II caches, and that implements an algorithm for invalidating the caches during given directory service operations. A directory service implementing this inventive mechanism is also described.
The foregoing has outlined some of the more pertinent objects of the present invention. These objects should be construed to be merely illustrative of some of the more prominent features and applications of the invention. Many other beneficial results can be attained by applying the disclosed invention in a different manner or modifying the invention as will be described. Accordingly, other objects and a fuller understanding of the invention may be had by referring to the following Detailed Description of the preferred embodiment.